package com.cheng.dataStructure.tree;

/**
 * @User Administrator
 * @Classname BinaryTreeDemo
 * @Project Data-structure-and-algorithm
 * @Description 二叉树的前序中序后序遍历
 * @Author wpcheng
 * @Create 2021-08-21-9:54
 * @Version 1.0
 */
public class BinaryTreeSearch {
    public static void main(String[] args) {

        //创建二叉树
        BinaryTree1 binaryTree = new BinaryTree1();
        //定义节点
        HeroNode1 root = new HeroNode1(1, "刘备");
        HeroNode1 node2 = new HeroNode1(2, "关羽");
        HeroNode1 node3 = new HeroNode1(3, "张飞");
        HeroNode1 node4 = new HeroNode1(4, "黄忠");
        HeroNode1 node5 = new HeroNode1(5, "马超");
        HeroNode1 node6 = new HeroNode1(6, "墨子");
        HeroNode1 node7 = new HeroNode1(7, "干将");
        //把节点插入到树中
        root.setLeft(node2);
        root.setRight(node3);
        node2.setRight(node4);
        node3.setRight(node5);
        node2.setLeft(node6);
        node4.setLeft(node7);

        binaryTree.setRoot(root);
        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();


        HeroNode1 search = binaryTree.preOrderSearch(4);
        if (search != null) {
            System.out.printf("找到了id=%d,name=%s 的节点信息", search.getId(), search.getName());
        } else {
            System.out.println("没找到");
        }
        HeroNode1 search1 = binaryTree.infixOrderSearch(4);
        if (search != null) {
            System.out.printf("找到了id=%d,name=%s 的节点信息", search.getId(), search.getName());
        } else {
            System.out.println("没找到");
        }

        HeroNode1 search2 = binaryTree.postOrderSearch(4);
        if (search != null) {
            System.out.printf("找到了id=%d,name=%s 的节点信息", search.getId(), search.getName());
        } else {
            System.out.println("没找到");
        }


    }

}

//定义二叉树BinaryTree
class BinaryTree1 {
    private HeroNode1 root;

    public void setRoot(HeroNode1 root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //前序查找
    public HeroNode1 preOrderSearch(int id) {
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        } else {
            return null;
        }
    }

    //中序查找
    public HeroNode1 infixOrderSearch(int id) {
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        } else {
            return null;
        }
    }

    //后序查找
    public HeroNode1 postOrderSearch(int id) {
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        } else {
            return null;
        }
    }
}

//定义二叉树的节点
class HeroNode1 {
    private int id;
    private String name;
    private HeroNode1 left;
    private HeroNode1 right;

    public HeroNode1(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode1 getLeft() {
        return left;
    }

    public void setLeft(HeroNode1 left) {
        this.left = left;
    }

    public HeroNode1 getRight() {
        return right;
    }

    public void setRight(HeroNode1 right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    //编写前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }
        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
    }

    //编写中序遍历方法
    public void infixOrder() {

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }
        //输出父节点
        System.out.println(this);

        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
    }

    //编写后序遍历方法
    public void postOrder() {

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }

        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
        //输出父节点
        System.out.println(this);
    }

    //前序查找
    public HeroNode1 preOrderSearch(int id) {
        //先比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        HeroNode1 resNode = null;
        //如果不是，再判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.preOrderSearch(id);
        }
        //若左节点递归查到，就返回
        if (resNode != null) {
            return resNode;
        }
        //若左节点递归没查到，就向右节点递归查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(id);
        }
        //向右节点递归查找后，查到就返回，查不到就返回null
        return resNode;
    }

    //中序查找
    public HeroNode1 infixOrderSearch(int id) {

        HeroNode1 resNode = null;
        //先判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(id);
        }
        //若左节点递归查到，就返回
        if (resNode != null) {
            return resNode;
        }
        //若左节点递归没查到，就比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        //若左节点递归没查到，就向右节点递归查找
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(id);
        }
        //向右节点递归查找后，查到就返回，查不到就返回null
        return resNode;
    }

    //后序查找
    public HeroNode1 postOrderSearch(int id) {

        HeroNode1 resNode = null;
        //先判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.postOrderSearch(id);
        }
        //若左节点递归没查到，就比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        //若左节点递归没查到，就向右节点递归查找，查到就直接返回
        if (this.right != null) {
            resNode = this.right.postOrderSearch(id);
        }

        //向右节点递归没查找，就比较当前节点，如果找的，则直接返回，不是就返回null
        if (resNode != null) {
            return this;
        }
        return resNode;

    }


}